import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class project {
    public String kthDistinct(String[] arr, int k) {
        Map<String,Integer> map=new HashMap<>();
        for(String s : arr){
            map.put(s,map.getOrDefault(s,0)+1);
        }
        LinkedList<String> list=new LinkedList<>();
        for(String s : arr){
            if(map.get(s)==1){
                list.add(s);
            }
        }
        return list.size()<k?"":list.get(k-1);
    }











    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for(String s : tokens){
            switch(s){
                case "+":
                case "-":
                case "*":
                case "/":
                    int a=stack.pop();
                    int b=stack.pop();
                    stack.push(sum(b,a,s));
                    break;
                default:
                    stack.push(Integer.parseInt(s));
            }
        }
        return stack.pop();
    }
    public int sum(int a,int b,String s){
        switch(s){
            case "+":
                return a+b;
            case "-":
                return a-b;
            case "*":
                return a*b;
            case "/":
                return a/b;
        }
        return -1;
    }








    public int numUniqueEmails(String[] emails) {
        Set<String> set=new HashSet<>();
        for(String s : emails){
            String[] str=s.split("@");
            String ss=str[0];
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<ss.length();i++){
                if(ss.charAt(i)=='.'){
                    continue;
                }else if(ss.charAt(i)=='+'){
                    break;
                }else{
                    sb.append(ss.charAt(i));
                }
            }
            sb.append("@"+str[1]);
            set.add(sb.toString());
        }
        return set.size();
    }











    public boolean isLongPressedName(String name, String typed) {
        if(name.equals(typed)){
            return true;
        }
        int i=0;
        int j=0;
        while(j<typed.length()){
            if(i<name.length()&&name.charAt(i)==typed.charAt(j)){
                j++;
                i++;
            }else if(j>0&&typed.charAt(j)==typed.charAt(j-1)){
                j++;
            }else {
                return false;
            }
        }
        return i==name.length();
    }









    public String[] uncommonFromSentences(String s1, String s2) {
        String[] str1=s1.split(" ");
        String[] str2=s2.split(" ");
        Map<String,Integer> map=new HashMap<>();
        for(String s : str1){
            if(map.get(s)==null){
                map.put(s,1);
            }else{
                map.put(s,map.get(s)+1);
            }
        }
        for(String s : str2){
            if(map.get(s)==null){
                map.put(s,1);
            }else{
                map.put(s,map.get(s)+1);
            }
        }
        List<String> list=new ArrayList<>();
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            if(entry.getValue()>1){
                continue;
            }
            list.add(entry.getKey());
        }
        return list.toArray(new String[list.size()]);
    }








    public boolean validMountainArray(int[] arr) {
        int i=0;
        int len=arr.length;
        while(i+1<len&&arr[i]<arr[i+1]){
            i++;
        }
        if(i==0||i==len-1){
            return false;
        }
        while(i+1<len&&arr[i]>arr[i+1]){
            i++;
        }
        return i==len-1;
    }













    int x;
    TreeNode xNode;
    int lenx=0;
    boolean boolx=false;

    int y;
    TreeNode yNode;
    int leny=0;
    boolean booly=false;
    public boolean isCousins(TreeNode root, int x, int y) {
        this.x=x;
        this.y=y;
        dfs(root,0,null);
        return lenx==leny&&yNode!=xNode;
    }
    public void dfs(TreeNode root,int len,TreeNode prev){
        if(root==null){
            return;
        }
        if(root.val==x) {
            xNode = prev;
            lenx = len;
            boolx = true;
        }else if(root.val==y){
            yNode=prev;
            leny=len;
            booly=true;
        }
        if(boolx&&booly){
            return;
        }
        dfs(root.left,len+1,root);
        if(boolx&&booly){
            return;
        }
        dfs(root.right,len+1,root);
    }










    public int findShortestSubArray(int[] nums) {
        Map<Integer,int[]> map=new HashMap<>();
        int sum=0;
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                map.get(nums[i])[0]++;
                map.get(nums[i])[2]=i;
            }else{
                map.put(nums[i],new int[]{1,i,i});
            }
        }
        int max=0;
        int min=0;
        for(Map.Entry<Integer,int[]> entry : map.entrySet()){
            int[] arr=entry.getValue();
            if(max<arr[0]){
                max=arr[0];
                min=arr[2]-arr[1]+1;
            }else if(max==arr[0]){
                if(min>arr[2]-arr[1]+1){
                    min=arr[2]-arr[1]+1;
                }
            }
        }
        return min;
    }













    public String addBinary(String a, String b) {
        StringBuilder sb=new StringBuilder();
        int len=Math.max(a.length(),b.length());
        int tmp=0;
        for(int i=0;i<len;i++){
            tmp+=i<a.length()?(a.charAt(a.length()-1-i)-'0'):0;
            tmp+=i<b.length()?(b.charAt(b.length()-1-i)-'0'):0;
            sb.append((char)(tmp%2+'0'));
            tmp/=2;
        }
        if(tmp>0){
            sb.append('1');
        }
        sb.reverse();
        return sb.toString();
    }













    public int numDifferentIntegers(String word) {
        Set<String> set=new HashSet<>();
        for(int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            if(Character.isDigit(ch)){
                StringBuilder sb=new StringBuilder();
                while(i<word.length()&&word.charAt(i)=='0') {
                    i++;
                }
                while(i<word.length()&&Character.isDigit(word.charAt(i))){
                    sb.append(word.charAt(i));
                    i++;
                }
                i-=1;
                set.add(sb.toString());
            }
        }
        return set.size();
    }
}
